package com.data2.java.show.datastructure;

/**
 * @author leewow
 * @description
 * @date 2020/9/10 下午10:57
 *
 * 1、红黑二叉树 - Red Black Tree - 是一种自平衡的二叉查找树（近似平衡，不是严格平衡）
 *
 * 1.节点是红色或黑色
 * 2.根节点是黑色
 * 3.每个叶子节点都是黑色的空节点nil,空节点意味着不存储数据
 * 4.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
 * 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
 *
 *
 * 这些规则保证了：红黑树从根到叶子结点的最长路径不会超过最短路径的2倍
 *
 * 2、变色、旋转
 *      当插入或删除节点的时候，这些规则可能会打破，需要变色、旋转保持还是红黑树
 *
 * 3、AVL与RBT的比较
 *
 * AVL 树是一种高度平衡的二叉树，所以查找的效率非常高，
 * 但是，有利就有弊，AVL 树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。
 * 所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。
 * 红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比 AVL 树要低。
 *
 * 4、时间复杂度
 *  AVL（严格平衡二叉树 - 高度log2n）、RBT（近似平衡二叉树 - 高度近似log2n）
 *        - 解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。
 *
 *  红黑树的高度近似log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。
 *
 * 5、应用场景：
 *      TreeMap
 *      TreeSet
 *      HashMap (java8)
 *
 * 6、跳表
 * 因为红黑树是一种性能非常稳定的二叉查找树，所以，在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到它。不过，它实现起来比较复杂，这个时候，我们其实更倾向用跳表来替代它
 *
 *
 * 7、动态数据结构
 * 动态数据结构是支持动态的更新操作，里面存储的数据是时刻在变化的，通俗一点讲，它不仅仅支持查询，还支持删除、插入数据。而且，这些操作都非常高效。如果不高效，也就算不上是有效的动态数据结构了。所以，这里的红黑树算一个，支持动态的插入、删除、查找，而且效率都很高。链表、队列、栈实际上算不上，因为操作非常有限，查询效率不高。
 *
 */
public class RBT {
}
